package com.huo.array;

import java.util.*;

/**
 * 稀疏数组
 * 第一行存储原始数据总行数，总列数，总的非0数据个数(行数=有效数据+1，列数是3，固定的)
 * 接下来每一行都存储非0数所在行，所在列，和具体值
 * 0 0 0 0       row col val
 * 0 1 0 0       4    4   3
 * 0 0 2 0       1    1   1
 * 0 0 3 0       2    2   2
 * 3    2   3
 */
public class SparseArray {

    /**
     * 转为稀疏数组的算法：
     * 1、遍历数组，得到有效元素的个数effectiveNum。
     * 2、创建稀疏数组，行数为effectiveNum+1。  int[effectiveNum+1][3]
     * 3、将有效数据存入稀疏数组即可。
     */
    public int[][] toSpaeseArray(int[][] arr, int invalidData) {
        final List<List<Integer>> effectiveList = getEffectiveList(arr, invalidData);
        //有效元素的个数
        final int effectiveNum = effectiveList.size();
        //创建稀疏数组
        final int[][] spaeseArray = new int[effectiveNum + 1][3];
        //赋值
        spaeseArray[0][0] = arr.length;
        spaeseArray[0][1] = arr[0].length;
        spaeseArray[0][2] = effectiveNum;
        for (int i = 1; i <= effectiveNum; i++) {
            spaeseArray[i][0] = effectiveList.get(i - 1).get(0);
            spaeseArray[i][1] = effectiveList.get(i - 1).get(1);
            spaeseArray[i][2] = effectiveList.get(i - 1).get(2);
        }
        return spaeseArray;
    }

    /**
     * 获取有效的数据
     *
     * @param arr
     * @param invalidData 无效的数据
     * @return 返回的list 下标分别对应的是  0：行  1：列  2：有效的数据
     */
    public List<List<Integer>> getEffectiveList(int[][] arr, int invalidData) {
        final List<List<Integer>> result = new ArrayList<>();
        if (arr.length == 0) {
            throw new RuntimeException("数组不能为空！");
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if (arr[i][j] != invalidData) {
                    final List<Integer> list = new ArrayList();
                    //行
                    list.add(i);
                    //列
                    list.add(j);
                    //值
                    list.add(arr[i][j]);
                    result.add(list);
                }
            }
        }
        return result;
    }

    /**
     * 稀疏数组转为原始数组
     * 1、获取第一行的数据，建立原始数组 arr= int[arr[0][0]][arr[0][1]]
     * 2、读取稀疏数组后几行数组，并赋给原始数组
     *
     * @param arr
     * @return
     */
    public int[][] spaeseArray2Array(int[][] arr, int invalidData) {
        final int[][] result = new int[arr[0][0]][arr[0][1]];
        Set<Integer> set = new HashSet<>();
        for (int i = 1; i < arr.length; i++) {
            result[arr[i][0]][arr[i][1]] = arr[i][2];
            set.add(arr[i][2]);
        }
        if (invalidData != 0) {
            for (int i = 0; i < result.length; i++) {
                for (int j = 0; j < result[i].length; j++) {
                    if (!set.contains(result[i][j])) {
                        result[i][j] = invalidData;
                    }
                }
            }
        }
        return result;

    }


    public static void main(String[] args) {
        final SparseArray sparseArray = new SparseArray();
        int[][] arr = Array.genert2DArray(5, 5, -1);
        Array.toString(arr);
        System.out.println("------------------------");
        int[][] arr1 = sparseArray.toSpaeseArray(arr, -1);
        Array.toString(arr1);
        System.out.println("------------------------");
        int[][] arr2 = sparseArray.spaeseArray2Array(arr1, -1);
        Array.toString(arr2);
    }

}
